package com.xcc.dataStructures.demo03_link;

import java.util.Stack;

/**
 * 单链表
 *
 * @author xiaocheng
 * @date 2020/11/19 22:35
 */
public class SingleLinkedDemo {

    public static void main(String[] args) {
        Node node1 = new Node(1, "宋江", "及时雨");
        Node node2 = new Node(2, "吴用", "智多星");
        Node node3 = new Node(3, "卢俊义", "玉麒麟");
        Node node4 = new Node(4, "林冲", "豹子头");

        SingLinkedList singLinkedList = new SingLinkedList();
        singLinkedList.add(node1);
        singLinkedList.add(node4);
        singLinkedList.add(node3);
        singLinkedList.add(node2);
        singLinkedList.list();

        /*singLinkList.del(5);
        System.out.println("删除之后的单链表为:");
        singLinkList.list();*/

        singLinkedList.update(new Node(4,"戴宗","神行太保"));
        System.out.println("修改之后的单链表为:");
        singLinkedList.list();

        System.out.println("单链表中有效节点的个数:");
        System.out.println(SingLinkedList.getLength(singLinkedList.getHead()));

        System.out.println("找单链表中的倒数第 k 个结点:");
        Node kNode = SingLinkedList.getByNum(singLinkedList.getHead(), 5);
        System.out.println(kNode);

        System.out.println("反转之后(改变结构)为:");
        singLinkedList.reverse();
        singLinkedList.list();

        System.out.println("反向遍历(不改变结构)为:");
        singLinkedList.reversePrint();
    }

}

/**
 * 单链表的管理
 */
class SingLinkedList {

    //定义头节点
    private Node head = new Node(0,"","");

    /**
     * 反向遍历
     */
    public void reversePrint() {
        //定义栈作为保存
        Stack<Node> nodes = new Stack<>();

        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            nodes.push(temp.next);
            temp = temp.next;
        }

        while (!nodes.empty()) {
            System.out.println(nodes.pop());
        }
    }

    /**
     * 反转（改变结构）
     */
    public void reverse(){
        //定义一个新的头节点
        Node reverse = new Node(-1,"","");
        //指针
        Node cur = head.next;
        //临时变量为当前节点
        Node temp = null;
        while (true) {
            if (cur == null) {
                break;
            }
            //当前值为指针指向的值
            temp = cur;
            //指针后移
            cur = cur.next;
            //当前节点为 头节点的下一个接待你
            temp.next = reverse.next;
            //头节点的下一个节点为当前接待你
            reverse.next = temp;
        }
        //将原始头节点下一个节点指向  新头节点的下一个节点
        head.next = reverse.next;
    }

    /**
     * 查找单链表中的倒数第 k 个结点
     */
    public static Node getByNum(Node head,int num){
        int k = getLength(head) - num;
        if (k < 0) {
            return new Node(-1,"k大于长度","-1");
        }
        Node temp = head.next;
        //判断是否找不到
        boolean flag = true;
        while (true) {
            if (temp == null) {
                flag = false;
                break;
            }
            if (k == 0) {
                break;
            }
            k--;
            temp = temp.next;
        }
        if (!flag) {
            //越界了，k为负数
            return new Node(-1,"k为负数","-1");
        }
        return temp;
    }

    /**
     * 求单链表中有效节点的个数
     */
    public static int getLength(Node head){
        int count = 0;
        Node temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            count++;
            temp = temp.next;
        }
        return count;
    }

    /**
     * 获取头节点
     */
    public Node getHead(){
        return head;
    }

    /**
     * 添加节点
     */
    public void add(Node node) {
        Node temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    /**
     * 按照顺序插入
     */
    public void addByOrder(Node node) {
        //需要添加的节点的前一个节点
        Node temp = head;
        boolean flag = true;
        while (true) {
            if (temp.next == null) {
                flag = false;
                break;
            }
            if (temp.next.no > node.no) {
                break;
            }
            temp = temp.next;
        }
        //插入数据
        node.next = temp.next;
        temp.next = node;
    }

    /**
     * 删除节点
     */
    public void del(int no) {
        //临时节点为需要删除节点的前一个节点
        Node temp = head;
        boolean flag = true; //标识是否已经寻找完毕
        while (true) {
            //如果已经遍历完毕
            if (temp.next == null) {
                flag = false;
                break;
            }
            //找到需要删除节点的上一个节点
            if (temp.next.no == no) {
                break;
            }
            temp = temp.next;
        }
        if (!flag) {
            System.out.println("找不到需要删除的节点!!!");
            return;
        }
        //删除对应的节点
        temp.next = temp.next.next;
    }

    /**
     * 修改节点
     */
    public void update(Node node) {
        //临时节点为需要修改节点的前一个节点
        Node temp = head;
        //判断是否在链表中找到对应的节点
        boolean flag = true;
        while (true) {
            //没有找到对应的节点
            if (temp.next == null) {
                flag = false;
                break;
            }
            //找到对应的节点
            if (temp.next.no == node.no) {
                break;
            }
            //后移
            temp = temp.next;
        }
        if (!flag) {
            System.out.println("找不到需要修改的节点!!!");
            return;
        }
        //修改
        node.next = temp.next.next;
        temp.next = node;
    }

    /**
     * 遍历单链表
     */
    public void list(){
        //第一个节点
        Node temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

/**
 * 节点
 */
class Node{

    public int no;
    public String name;
    public String nickname;
    public Node next;

    //定义初始节点
    public Node(int no,String name,String nickname){
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "Node[" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                ']';
    }
}